#pragma once


namespace Sim
{
    struct BKDRHash
    {
        size_t operator()(const string& s)
        {
            size_t hash = 0;
            for (auto ch : s)
            {
                hash = hash * 131 + ch;
            }
            return hash;
        }
    };



    struct APHash
    {
        size_t operator()(const string& s)
        {
            size_t hash = 0;
            for (size_t i = 0; i < s.size(); i++)
            {
                char ch = s[i];
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
                }
            }
            return hash;
        }
    };
    
    struct DJBHash
    {
        size_t operator()(const string& s)
        {
            size_t hash = 5381;
            for (auto ch : s)
            {
                hash += (hash << 5) + ch;
            }
            return hash;
        }
    };




    template<size_t N,
			class K = string,
			class Hash1 = BKDRHash,
            class Hash2 = APHash,
            class Hash3 = DJBHash>
	class BloomFilter
	{
	public:
		void set(const K& key)
		{
            size_t hash1 = Hash1()(key) % N;
            _bs.set(hash1);
            size_t hash2 = Hash2()(key) % N;
            _bs.set(hash2);
            size_t hash3 = Hash3()(key) % N;
            _bs.set(hash3);

            //cout << hash1 << " " << hash2 << " " << hash3 << endl;
		}
        bool test(const K& key)
        {
            size_t hash1 = Hash1()(key) % N;
            if (!_bs.test(hash1))
            {
                return false;
            }
            size_t hash2 = Hash2()(key) % N;
            if (!_bs.test(hash2))
            {
                return false;
            }
            size_t hash3 = Hash3()(key) % N;
            if (!_bs.test(hash3))
            {
                return false;
            }
            return true;
        }
	private:
		std::bitset<N> _bs;
	};
};